package com.Nov_Four;

public class Solution1774 {

    int target;
    int best=(int)1e9;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.target=target;
        for (int baseCost : baseCosts) {
            backtracking(toppingCosts, 0, baseCost);
        }
        return best;
    }

    public void backtracking(int[] toppingCosts,int idx,int total){
        int sum=Math.abs(best-target)-Math.abs(total-target);
        if (sum>0||(sum==0&&total<best)){
            best=total;
        }
        if (total>=target||idx==toppingCosts.length){
            return;
        }
        for (int i = 0; i < 3; i++) {
            backtracking(toppingCosts,idx+1,total+toppingCosts[idx]*i);
        }
    }

    public static void main(String[] args) {
        Solution1774 solution1774=new Solution1774();
        System.out.println(solution1774.closestCost(new int[]{1,7},new int[]{3,4},10));
    }

}
